1. Field of the Invention
This invention relates to the field of information networks, and more particularly relates to a method and apparatus for identifying duplicate packets.
2. Description of the Related Art
As more and more information is transferred over today's networks, businesses have come to rely heavily on their network infrastructure in providing their customers with timely service and information. Failures in such network infrastructures can be costly both in terms of lost revenue and idled employees. Thus, high reliability systems are becoming increasingly attractive to users of networking equipment. Moreover, the manufacturers of routers, switches and other such network elements are constantly called upon to provide network elements that support ever-increasing network traffic loads, while still maintaining such high reliability. These demands force network elements to provide increased packet processing rates, typically through substantial increases in processing power.
For network environments requiring such high availability, one approach to providing failsafe connections is to transmit each packet multiple times, once over several (or all) independents paths from source to destination. With independent paths, it is normally sufficient to provide two paths and transmit the packet just twice because of the low probability of these two paths failing simultaneously. This approach provides essentially zero fail-over time, because, if one path fails, a copy of the packet is received on the other path (at least, with high probability).
In contrast, other schemes typically entail some sort of delay. This may include delays such as the delay associated with the detection of the active path's failure, the delay associated with switching packet forwarding to an alternative path and the delay associated with the retransmission of packet traffic that was dropped during the switchover (which is normally handled by end hosts). This delay can stretch into seconds, as a result of protocol timeouts and settling time for routing reconfiguration, particularly over long-haul links.
Thus, despite the attractions of multiple packet transmission techniques over other alternatives, such approaches present a number of challenges. One issue is the extra bandwidth required to send each packet twice. However, the second path's bandwidth is required in any case on failure of the first, so one can often argue that this bandwidth is being wasted in the absence of failure in any case, either by being left idle (and so available for use in the event of a failure) or by transporting these duplicates (which are used in the event of a failure). A second challenge is directing packets on two independent paths. In the case of separate Layer 1 paths, there are normally two physical links out of the source, such as two fiber optic connections between source and destination, such that the duplicate transmission takes place at the physical MAC layer. At higher layers, the source may be able to “source route” the packet along two independent paths using the facilities provided by those layers. For example, an enterprise router may be connected to two separate service providers (SPs) and transmit the packet simultaneously over the link to each separate SP. In addition, the internet protocol (IP) Loose Source Route Option (LSRO) and multiple path label switching (MPLS) can be used in environments that support such mechanisms.
It should be noted that, in providing a reliable connection in the manner outlined above, such a technique must prevent duplicate packets from being delivered to the end host. This is of particular relevance when providing this availability feature in the network layer, transparent to end hosts (which typically connect subnets over some exposed long-haul connection), because the duplicate packets consume resources at the end host and on the end host's network. Moreover, in some cases, these duplicate packets can interfere with the operation of the end host's protocols. Such duplicate packets also violate the standard semantics of the network layer as a service, which is not supposed to duplicate packets. However, the network layer cannot rely on a sequence number to detect duplicates, such as that available in reliable transport protocols (e.g., the transport control protocol (TCP)).
What is therefore desired is the ability to provide reliable network connectivity through the transmission of duplicate packets along different paths without adversely affecting network efficiency significantly. Such functionality should also be provided in a manner that does not adversely impact the processing capabilities (i.e., packet throughput) of network elements employing such a solution. Preferably, a network element employing such a solution should also be capable of defending both itself and the network against attacks that employ large numbers of packets to disrupt network operations.